/*
题目: 打开转盘锁
你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以自由旋转：例如把 '9' 变为 '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。

锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。

列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。

字符串 target 代表可以解锁的数字，你需要给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1 。

https://leetcode.cn/problems/open-the-lock
 */
public class OpenLock {
    Set<String> death = new HashSet<> ();

    public int openLock(String[] deadends, String target) {
        for (String x : deadends)   death.add(x);

        if ("0000".equals(target))  return 0;
        if (death.contains(target) || death.contains("0000")) return -1;

        // 双向广搜
        // 同时从 起点 和 终点 出发, 第一次有 交集 表示最短路径
        Queue<String> frontQue = new LinkedList<> ();
        Queue<String> backQue = new LinkedList<> ();

        // 记录 到达某个 字符串 用了 多少步
        Map<String, Integer> frontMap = new HashMap<> ();
        Map<String, Integer> backMap = new HashMap<> ();

        // 必须两个都不为空, 才能 互通
        frontQue.offer("0000");
        backQue.offer(target);
        frontMap.put("0000", 0);
        backMap.put(target, 0);
        // 两个都为空, 说明无法互通
        while (!frontQue.isEmpty() && !backQue.isEmpty()) {
            // 每次都从 路径少的 队列出发, 尽量平均两个方向
            int ret = -1;
            if (frontQue.size() <= backQue.size()) {
                ret = update(frontQue, frontMap, backMap);
            } else {
                ret = update(backQue, backMap, frontMap);
            }

            if (ret != -1) return ret;
        }

        return -1;
    }

    // 定义 : map 是 queue 对应的 哈希表, anther 是 queue 对应的 哈希表
    private int update(Queue<String> queue, Map<String, Integer> map, Map<String, Integer> another) {
        int size = queue.size();
        while (size -- > 0) {
            String cur = queue.poll();
            char[] cs = cur.toCharArray();
            int steps = map.get(cur);    // 得到 到达 cur 的 步数

            for (int i = 0; i < 4; i ++) {
                // 每次可以向上拨动, 或者向下拨动
                for (int j = -1; j <= 1; j ++) {
                    char t = cs[i]; // 应该放在里面

                    if (j == 0) continue ;

                    if (cs[i] == '9' && j == 1) cs[i] = '0';
                    else if (cs[i] == '0' && j == -1) cs[i] = '9';
                    else    cs[i] = (char) (cs[i] + j);

                    String str = String.valueOf(cs);  // 这里不能是 toString, char[] 中的 toString 会将方括号已经转成字符串
                    cs[i] = t;

                    // 当前 map 已经记录过了 或者 在 名单 里面
                    if (map.containsKey(str) || death.contains(str)) continue ;

                    // map 刚好探索到这, 另一个 哈希表 已经有记录了, 所有这是 碰头 的最少操作步数
                    if (another.containsKey(str)) {
                        return steps + another.get(str) + 1;  // 到达 cur + 另一个str + 1(cur 到 str)
                    } else {
                        queue.offer(str);
                        map.put(str, steps + 1);
                    }
                }
            }
        }
        return -1;  // -1 表示到此为止, 还没有找到
    }
}

